//-------------------------------------------------------------------
//	Copyright (c) 2010-2014  Zhirnov Andrey
//	This file is part of the "UX Standard Lib" project.
//	See copyright notice in "UX_STL_Core.h".
//-------------------------------------------------------------------

#ifndef _UXS_SET_TYPE_H
#define _UXS_SET_TYPE_H

#pragma once

#include "TAllocator.h"
#include "CopyStrategy.h"
#include "TArray.h"

namespace UX_STL
{
namespace UXTypes
{


	//
	// Set
	//

#	define TSet	set
	
	template <	typename Value,
				typename S = TCopyStrategy< Value >,
				typename A = TAllocator< Value >
			 >
	struct TSet
	{
		friend struct MemMover;

	// types
	public:
		typedef TSet< Value, S, A >			Self;

		typedef Value						key_t;
		typedef Value						value_t;

		typedef Ptr< const Value >			value_cptr_t;

		typedef uni_array< Value >			values_range_t;
		typedef uni_array< const Value >	const_values_range_t;


	private:
		typedef array< Value, S, A >		node_array_t;

		template <typename Key>
		struct TValueSearchCmp
		{
			const Key &	_key;
			///
			TValueSearchCmp (const Key &k): _key(k) {}

			bool operator == (const Value &value) const
			{
				return UXMath::All( _key == value );
			}

			bool operator != (const Value &value) const
			{
				return not ( *this == value );
			}

			bool operator <  (const Value &value) const
			{
				return UXMath::All( _key < value );
			}

			bool operator >  (const Value &value) const
			{
				return UXMath::All( _key > value );
			}
			
			bool operator >= (const Value &value) const
			{
				return UXMath::All( not ( _key < value ) );
			}
		};


	// variables
	protected:
		node_array_t	_aNodes;


	// methods
	public:
		TSet ()
		{}

		TSet (const Self &other) : _aNodes( other._aNodes )
		{}
		
		RVALUE_REFERENCE_ONLY(
			TSet (Self &&other) : _aNodes( ToRValueRef( other._aNodes ) )
			{}
		)


		Value const &	operator [] (usize i) const
		{
			return ReferenceCast< const Value >( _aNodes[i] );
		}
		
		template <typename Key>
		Value const &	operator () (const Key &key) const
		{
			usize	idx;
			FindIndex( key, idx );
			return (*this)[ idx ];
		}

		Self &			operator << (Value &value)
		{
			Add( value );
			return *this;
		}

		template <typename V>
		Self &			operator << (const V &value)
		{
			Add( Value(value) );
			return *this;
		}


		bool			operator == (const Self &right) const
		{
			return _aNodes == right._aNodes;
		}

		bool			operator != (const Self &right) const
		{
			return not (*this == right);
		}


		Value const &	Front ()		const	{ return (*this)[0]; }
		Value const &	Back ()			const	{ return (*this)[ LastIndex() ]; }

		Value const *	ptr()			const	{ return (Value const *) _aNodes.ptr(); }

		bool			Empty ()		const	{ return _aNodes.Empty(); }
		usize			Count ()		const	{ return _aNodes.Count(); }
		usize			LastIndex ()	const	{ return _aNodes.LastIndex(); }
		usize			Size ()			const	{ return _aNodes.Size(); }


		usize Add (const Value &value)
		{
			typedef TValueSearchCmp< Value >	cmp_t;
			return _Add< cmp_t >( value );
		}


		usize AddOrReplace (const Value &value)
		{
			typedef TValueSearchCmp< Value >	cmp_t;
			return _AddOrReplace< TValueSearchCmp< cmp_t > >( value );
		}


		template <typename Key>
		bool FindIndex (const Key &key, OUT usize &idx) const
		{
			typedef TValueSearchCmp< Key >	cmp_t;
			return _FindIndex< cmp_t >( key, idx );
		}


		template <typename Key>
		bool FindFirstIndex (const Key &key, OUT usize &idx) const
		{
			return FindIndex( key, idx );
		}


		void FindLastIndex (usize first, OUT usize &idx) const
		{
			key_t const &	key = (*this)[first].first;

			idx = first;

			for (usize i = first+1; i < this->Count()-1 and key == (*this)[i].first; ++i)
			{
				idx = i;
			}
		}


		template <typename Key>
		bool IsExist (const Key &key) const
		{
			usize idx = 0;
			return FindIndex( key, idx );
		}

		
		template <typename Key>
		bool Find (const Key &key, OUT value_cptr_t & result) const
		{
			usize	idx = -1;

			if ( not FindIndex( key, idx ) )
				return false;

			result = &_aNodes[ idx ];
			return true;
		}


		template <typename Key>
		bool FindAll (const Key &key, OUT values_range_t &result)
		{
			usize	first;
			usize	last;

			if ( not FindFirstIndex( key, first ) )
				return false;
			
			FindLastIndex( first, last );

			result = values_range_t( ptr() + first, last - first + 1 );
			return true;
		}


		template <typename Key>
		bool FindAll (const Key &key, OUT const_values_range_t &result) const
		{
			usize	first;
			usize	last;

			if ( not FindFirstIndex( key, first ) )
				return false;
			
			FindLastIndex( first, last );

			result = const_values_range_t( ptr() + first, last - first + 1 );
			return true;
		}


		values_range_t  GetRange (usize first, usize last)
		{
			return _aNodes.SubArray( first, first + last + 1 );
		}


		const_values_range_t  GetRange (usize first, usize last) const
		{
			return _aNodes.SubArray( first, first + last + 1 );
		}


		template <typename Key>
		bool Erase (const Key &key)
		{
			usize	idx = -1;

			if ( not FindIndex( key, idx ) )
				return false;

			_aNodes.Erase( idx );
			return true;
		}


		void EraseFromIndex (usize index)
		{
			_aNodes.Erase( index );
		}


		void Clear ()
		{
			_aNodes.Clear();
		}


		void ClearMem ()
		{
			_aNodes.ClearMem();
		}


		void Resize (usize uSize)
		{
			_aNodes.Resize( uSize, false );
		}


		void Reserve (usize uSize)
		{
			_aNodes.Reserve( uSize );
		}


		void SwapMem (Self &other)
		{
			_aNodes.SwapMem( other._aNodes );
		}


	private:
		template <typename SearchCmp>
		void _GetIndexBounds (const SearchCmp &cmp, OUT usize &left, OUT usize &right) const
		{
			ASSERT( not _aNodes.Empty() );
	
			// binary search
			left  = 0;
			right = _aNodes.Count() - 1;
	
			while ( right - left > 1 )
			{
				usize	mid = (right + left) >> 1;

				if ( cmp > _aNodes[mid] )
					left = mid;
				else
					right = mid;
			}
		}


		template <typename SearchCmp>
		usize _Add (const value_t &value)
		{
			if ( _aNodes.Empty() )
			{
				_aNodes.PushBack( value );
				return _aNodes.LastIndex();
			}

			usize		left,
						right;
			SearchCmp	cmp( value );

			_GetIndexBounds( cmp, left, right );

			for (usize i = left; i < right; ++i)
			{
				if ( cmp >= _aNodes[i] and cmp < _aNodes[i+1] ) {
					_aNodes.Insert( value, i+1 );
					return i+1;
				}
			}

			if ( cmp == _aNodes[right] )
			{
				for (; right < _aNodes.Count() and cmp == _aNodes[right]; ++right) {}

				_aNodes.Insert( value, right );
				return right;
			}

			if ( cmp > _aNodes[right] )
			{
				_aNodes.Insert( value, right+1 );
				return right+1;
			}
			
			if ( cmp < _aNodes[left] )
			{
				_aNodes.Insert( value, left );
				return left;
			}

			WARNING( "" );
			return usize(-1);
		}
		

		template <typename SearchCmp>
		usize _AddOrReplace (const value_t &value)
		{
			if ( _aNodes.Empty() )
			{
				_aNodes.PushBack( value );
				return _aNodes.LastIndex();
			}
			
			usize		left,
						right;
			SearchCmp	cmp( value );

			_GetIndexBounds( cmp, left, right );
			
			for (usize i = left; i < right; ++i)
			{
				if ( cmp == _aNodes[i] ) {
					_aNodes[i] = value;
					return i;
				}

				if ( cmp > _aNodes[i] and cmp < _aNodes[i+1] ) {
					_aNodes.Insert( value, i+1 );
					return i+1;
				}
			}

			if ( cmp == _aNodes[right] )
			{
				_aNodes[right] = value;
				return right;
			}

			if ( cmp > _aNodes[right] )
			{
				_aNodes.Insert( value, right+1 );
				return right+1;
			}
			
			if ( cmp < _aNodes[left] )
			{
				_aNodes.Insert( value, left );
				return left;
			}
			
			WARNING( "" );
			return usize(-1);
		}


		template <typename SearchCmp, typename Key>
		bool _FindIndex (const Key &key, usize &idx) const
		{
			idx = usize(-1);

			if ( _aNodes.Empty() )
				return false;

			// binary search
			usize			left  = 0,
							right = _aNodes.LastIndex();
			SearchCmp		cmp( key );
			
			while ( right - left > 1 )
			{
				usize	mid = (left + right) >> 1;

				if ( cmp > _aNodes[mid] )
					left = mid;
				else
					right = mid;
			}

			for (usize i = 0; i < 2 and left+i <= right; ++i)
			{
				if ( cmp == _aNodes[left+i] )
				{
					idx = left+i;
					return true;
				}
			}

			return false;
		}
	};

#	undef TSet


//-------------------------------------------------------------------

}	// UXTypes
}	// UX_STL

#endif	// _UXS_SET_TYPE_H